package com.zk.algorithm.array;

import com.zk.algorithm.annotation.JianZhiOffer;

/**
 * 因子只包含 2，3，5 称为丑数
 *
 * @author zk
 */
@JianZhiOffer("34")
public class UglyNumber {

    // =============================
    // 方法一
    // =============================

    private boolean isUglyNumber(int number) {
        while (number % 2 == 0) {
            number /= 2;
        }

        while (number % 3 == 0) {
            number /= 3;
        }

        while (number % 5 == 0) {
            number /= 5;
        }

        // 1 当做第一个丑数
        return number == 1 ? true : false;
    }

    // 获取第 n 个丑数
    public int getNthUglyNumber(int n) {
        if (n <= 0) {
            return 0;
        }

        int number = 0;
        int count = 0;

        while (count < n) {
            number++;

            if (isUglyNumber(number)) {
                count++;
            }
        }

        return number;
    }

    // =============================
    // 方法二: DP
    // =============================

    // 丑数序列: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, …
    // 切成三组:
    //
    // (1) 1×2, 2×2, 3×2, 4×2, 5×2, …
    // (2) 1×3, 2×3, 3×3, 4×3, 5×3, …
    // (3) 1×5, 2×5, 3×5, 4×5, 5×5, …
    //
    //    initialize
    //    ugly[] =  | 1 |
    //    i2 =  i3 = i5 = 0;
    //
    //    First iteration
    //    ugly[1] = Min(ugly[i2]*2, ugly[i3]*3, ugly[i5]*5)
    //            = Min(2, 3, 5)
    //            = 2
    //    ugly[] =  | 1 | 2 |
    //    i2 = 1,  i3 = i5 = 0  (i2 got incremented )
    //
    //    Second iteration
    //    ugly[2] = Min(ugly[i2]*2, ugly[i3]*3, ugly[i5]*5)
    //             = Min(4, 3, 5)
    //             = 3
    //    ugly[] =  | 1 | 2 | 3 |
    //    i2 = 1,  i3 =  1, i5 = 0  (i3 got incremented )
    //
    //    Third iteration
    //    ugly[3] = Min(ugly[i2]*2, ugly[i3]*3, ugly[i5]*5)
    //             = Min(4, 6, 5)
    //             = 4
    //    ugly[] =  | 1 | 2 | 3 |  4 |
    //    i2 = 2,  i3 =  1, i5 = 0  (i2 got incremented )
    //
    //    Fourth iteration
    //    ugly[4] = Min(ugly[i2]*2, ugly[i3]*3, ugly[i5]*5)
    //              = Min(6, 6, 5)
    //              = 5
    //    ugly[] =  | 1 | 2 | 3 |  4 | 5 |
    //    i2 = 2,  i3 =  1, i5 = 1  (i5 got incremented )
    //
    //    Fifth iteration
    //    ugly[4] = Min(ugly[i2]*2, ugly[i3]*3, ugly[i5]*5)
    //              = Min(6, 6, 10)
    //              = 6
    //    ugly[] =  | 1 | 2 | 3 |  4 | 5 | 6 |
    //    i2 = 3,  i3 =  2, i5 = 1  (i2 and i3 got incremented )
    //
    //    Will continue same way till I < 150
    public int getNthUglyNo(int n) {
        int ugly[] = new int[n];  // To store ugly numbers

        int i2 = 0, i3 = 0, i5 = 0;

        int nextMultipleOf2 = 2;
        int nextMultipleOf3 = 3;
        int nextMultipleOf5 = 5;
        int nextUglyNo = 1;

        ugly[0] = 1;

        for (int i = 1; i < n; i++) {
            nextUglyNo = Math.min(nextMultipleOf2, Math.min(nextMultipleOf3, nextMultipleOf5));
            ugly[i] = nextUglyNo;

            if (nextUglyNo == nextMultipleOf2) {
                i2 = i2 + 1;
                nextMultipleOf2 = ugly[i2] * 2;
            } else if (nextUglyNo == nextMultipleOf3) {
                i3 = i3 + 1;
                nextMultipleOf3 = ugly[i3] * 3;
            } else if (nextUglyNo == nextMultipleOf5) {
                i5 = i5 + 1;
                nextMultipleOf5 = ugly[i5] * 5;
            }

        } /*End of for loop (i=1; i<n; i++) */

        return nextUglyNo;
    }

}
